#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/10/17 15:26
# ===========================================
#       题目名称： 61. 旋转链表
#       题目地址： https://leetcode.cn/problems/rotate-list/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================
from typing import *
from utils import *


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1. 判断是否只有一条或者 1条没有
        if not head or not head.next or k == 0:
            return head
        # 2. 先判断链表中有多少个元素 如果 k % len(head)
        size = 1
        tmp_head = head.next
        while tmp_head:
            tmp_head = tmp_head.next
            size += 1
        k = k % size
        while k > 0:
            tmp_head = head.next
            change_val,tmp_head.val = tmp_head.val, head.val
            while tmp_head.next:
                tmp_head = tmp_head.next
                tmp_head.val, change_val = change_val, tmp_head.val
            head.val = change_val
            k -= 1

        return head


if __name__ == '__main__':
    s = Solution()
    # [4,5,1,2,3]
    print("head = [1,2,3,4,5], k = 2 =>", StringUtils.to_string(
        s.rotateRight(head=ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))), k=2)))
    # [2,0,1]
    print("head = [0,1,2], k = 4 =>", StringUtils.to_string(
        s.rotateRight(head=ListNode(0, ListNode(1, ListNode(2))), k=4)))
    # []
    print("head = [], k = 0 =>", StringUtils.to_string(
        s.rotateRight(head=ListNode(), k=4)))
    # [1,2]
    print("head = [1,2], k = 1 =>", StringUtils.to_string(
        s.rotateRight(head=ListNode(1, ListNode(2)), k=1)))
